package day190818;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2019/8/18 上午 10:11
 */
public class MaximalSquare {

    public int maximalSquare(char[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int m = matrix.length, n = matrix[0].length, maxSide = 0;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (matrix[i - 1][j - 1] == '1') {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j]));
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }
        return maxSide * maxSide;
    }

    public static void main(String[] args) {
        char[][] chars = new char[][]{{'0','0','0','1'},
                                    {'1','1','1','0'},
                                    {'1','1','1','1'},
                                    {'1','1','1','1'},
                                    {'1','1','1','1'}};
//        char[][] chars = new char[][]{{'1', '1'},
//                {'1', '1'}};
        MaximalSquare square = new MaximalSquare();
        square.maximalSquare(chars);
    }

    public int countCharacters(String[] words, String chars) {
        int[] map = new int[26];
        int maxLength = 0;
        char[] charArray = chars.toCharArray();
        for (char c : charArray) {
            map[c - 'a']++;
        }
        for (String word : words) {
            char[] toCharArray = word.toCharArray();
            int length = word.length();
            int tempLength = 0;
            int[] tempMap = Arrays.copyOf(map, map.length);
            for (char c : toCharArray) {
                if (tempMap[c - 'a'] > 0) {
                    tempLength++;
                    tempMap[c - 'a']--;
                }
            }
            if (tempLength == length) {
                maxLength += length;
            }
        }
        return maxLength;
    }

    int[] cellValue = new int[6000];
    public int maxLevelSum(TreeNode root) {
        int maxCell = 0, maxVal = Integer.MIN_VALUE;
        if (root == null) {
            return maxCell;
        }
        maxCell = 1;
        maxVal = root.val;
        getCellValue(root, 1);
        for (int i = 1; i < cellValue.length; i++) {
            if (cellValue[i] > maxVal) {
                maxVal = cellValue[i];
                maxCell = i;
            }
        }
        return maxCell;
    }

    private void getCellValue(TreeNode root, int cell) {
        if (root.left != null) {
            getCellValue(root.left, cell + 1);
        }
        if (root.right != null) {
            getCellValue(root.right, cell + 1);
        }
        cellValue[cell] += root.val;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public String lastSubstring(String s) {
        HashSet<String> set = new HashSet<>();
        ArrayList<String> list = new ArrayList<>();
        char[] chars = s.toCharArray();
        int c = 0;
        for (int i = 0; i < chars.length; i++) {
            char aChar = chars[i];
            if (aChar - 'a' > c) {
                c = aChar - 'a';
            }
        }
        if (c == 0) {
            return s;
        }
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) - 'a' == c) {
                String substring = s.substring(i);

                if (!set.contains(substring)) {
                    set.add(substring);
                    list.add(substring);
                }
            }
        }

        Collections.sort(list);
        return list.get(list.size() - 1);
    }
}
